package com.example.interview.algorithm;

import java.util.Iterator;
import java.util.Stack;

/**
 * 用2个栈实现队列
 * @Description: TODO
 * @author gaobing
 * @date 2018年9月28日 上午11:04:26
 * 题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail 和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
 */
public class Test08Stack {

	public static class MList<T>{
		// 插入栈，只用于插入数据
		private Stack<T> stackOfPush=new Stack<>();
		// 弹出栈，只用于弹出数据
		private Stack<T> stackOfPop=new Stack<>();
		
		//添加操作，在队列尾部插入节点
		public void appendTail(T t) {
			stackOfPush.add(t); 
		}
		//删除操作，在队列头部删除节点
		public T deleteHead() {
			//先判断弹出栈是否为空，如果为空就将插入栈的所有数据 压到 弹出栈 ，此时弹出栈的数据就是先进先出的顺序
			if (stackOfPop.isEmpty()) {
				while(!stackOfPush.isEmpty()) {
					stackOfPop.add(stackOfPush.pop());
				}
			}
			//如果弹出栈没有数据弹出异常
			if (stackOfPop.isEmpty()) {
				throw new RuntimeException("no more element");
			}
			//返回弹出栈的栈顶元素，对应的就是队首的元素
			T pop= stackOfPop.pop();
			System.out.println(pop);
			return pop;
		}
		
		public void print() {
			for (Iterator iterator = stackOfPush.iterator(); iterator.hasNext();) {
				T push = (T) iterator.next();
				System.out.println(push);
			}
		}
		 
	}
	
	public static void main(String[] args) {
		MList<Integer> mList=new MList<>();
		mList.appendTail(1);
		mList.print();
		mList.appendTail(2);
		mList.print();
		mList.appendTail(3);
		mList.print();
		mList.deleteHead();
		mList.appendTail(4);
		mList.print();
		mList.deleteHead(); 
		mList.deleteHead();
		mList.deleteHead();
	}
}
